#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+10,SQRTN = 700;
int a[N];
struct BLOCK{
    int lmt;
    int block;
    int tot;
    int sum1[N];
    int sum2[SQRTN];
    int bl[N];
    void init(int n){
        lmt = n;
        block = sqrt(n);
        tot = n/block + (n % block != 0);
        for(int i = 1;i<=tot;i++){
            int lp = (i - 1)*block + 1,rp = min(n,block * i);
            for(int j = lp;j <= rp;j++){
                bl[j] = i;
            }
        }
    }
    void update(int x,int v){
        int p = bl[x];
        int lp = (p - 1)*block + 1;
        for(int i = x;i >= lp;i--){
            sum1[i] += v;
        }
        for(int i = p - 1;i >= 1;i--){
            sum2[i] += v;
        }   
    }
    inline int query(int x){
        int p = bl[x];
        return sum2[p] + sum1[x];
    }
} vb;
int ac[N];
int ql[N],qr[N],qidx[N];
int bl[N];
int block;
int tot;
bool cmp(int x,int y){
    return bl[ql[x]] < bl[ql[y]] || bl[ql[x]] == bl[ql[y]] && qr[x] < qr[y];
}
long long ans[N];
struct command1{
    int r,p,w;
    bool f;
    friend bool operator<(command1 a,command1 b){
        return a.r < b.r;
    }
};
struct command2{
    int l,r,p,w;
    bool f;
};
vector<command1> v1[N];
vector<command2> v2[N];
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n,m;
    cin>>n>>m;
    for(int i = 1;i<=n;i++){
        cin>>a[i];
        ac[i] = a[i];
    }
    sort(ac + 1,ac + 1 + n);
    int ncnt = unique(ac + 1,ac + 1 + n) - ac - 1;
    for(int i = 1;i<=n;i++){
        a[i] = lower_bound(ac + 1,ac + 1 + ncnt,a[i]) - ac;
    }
    vb.init(ncnt + 1);
    for(int i = 1;i<=m;i++){
        cin>>ql[i]>>qr[i];
        qidx[i] = i;
    }
    block = sqrt(n);
    tot = n / block + (n % block != 0);
    for(int j = 1;j <= tot;j++){
        int lp = (j - 1) * block + 1,rp = min(j * block,n);
        for(int i = lp;i <= rp;i++){
            bl[i] = j;
        }
    }
    sort(qidx + 1,qidx + 1 + m,cmp);
    int cl = 1,cr = 0;
    for(int p = 1;p <= m;p++){
        int l = ql[qidx[p]],r = qr[qidx[p]];
        /*
        while(cr < r){
            cr++;
            times[cl - 1].push_back({qidx[p],a[cr] + 1,-1});
            times[cr - 1].push_back({qidx[p],a[cr] + 1,1});   
        }*/
        if(cr < r){
            v2[cl - 1].push_back({cr + 1,r,qidx[p],-1,1});
            v1[cr].push_back({r - 1,qidx[p],1,1});
        }
        /* 
        while(cr > r){
            times[cl - 1].push_back({qidx[p],a[cr] + 1,1});
            times[cr - 1].push_back({qidx[p],a[cr] + 1,-1});
            cr--;
        }*/
        if(cr > r){
            v2[cl - 1].push_back({r + 1,cr,qidx[p],1,1});
            v1[r].push_back({cr - 1,qidx[p],-1,1});
        }
        /*
        while(cl < l){
            times[cl].push_back({qidx[p],a[cl],-1});
            times[cr].push_back({qidx[p],a[cl],1});
            ans[qidx[p]] -= cr - cl;
            cl++;
        }*/
        cr = r;
        if(cl < l){
            v2[cr].push_back({cl,l - 1,qidx[p],1,0});
            v1[cl].push_back({l - 1,qidx[p],-1,0});
            ans[qidx[p]] -= 1ll*(l - cl)*cr - 1ll*(cl + l - 1)*(l - cl)/2;
        }
        /*
        while(cl > l){
            cl--;
            times[cl].push_back({qidx[p],a[cl],1});
            times[cr].push_back({qidx[p],a[cl],-1});
            ans[qidx[p]] += cr - cl;
        }*/
        if(cl > l){
            v2[cr].push_back({l,cl - 1,qidx[p],-1,0});
            v1[l].push_back({cl - 1,qidx[p],1,0});
            ans[qidx[p]] += 1ll*(cl - l)*cr - 1ll*(cl - 1 + l)*(cl - l)/2;
        }
        cl = l;
    }
    multiset<command1> se;
    for(command1 v : v1[0]){
        se.insert(v);
    }
    for(int i = 1;i <= n;i++){
        vb.update(a[i],1);
        for(command1 v : v1[i]){
            se.insert(v);
        }
        while(se.size() && se.begin()->r < i){
            se.erase(se.begin());
        }
        for(command1 v : se){
            ans[v.p] += vb.query(a[i + v.f] + v.f)*v.w;
        }
        for(command2 v : v2[i]){
            for(int j = v.l;j <= v.r;j++){
                ans[v.p] += vb.query(a[j] + v.f) * v.w;
            }
        }
    }
    for(int i = 1;i<=m;i++){
        ans[qidx[i]] += ans[qidx[i - 1]];
    }
    for(int i = 1;i<=m;i++) {
        cout<<ans[i]<<'\n';
    }
}